package cn.edu.besti.cs1723.TX2305;

import eighthweek.AVLTree;
import ninthweek.ArrayHeap;

public class Sorting {
     //选择排序
    public static <T extends Comparable<? super T>> void selectionSort(T[] data) {
            int min;
            T temp;
            for (int i = 0; i < data.length - 1; i++) {
                min = i;
                for (int j = i + 1; j < data.length; j++) {
                    if (data[min].compareTo(data[j]) > 0) {
                        min = j;
                    }
                }
                // 交换
                swap(data, min, i);
            }

        }
    //插入排序
    public static <T extends Comparable<? super T>> void insertionSort(T[] data) {
            for (int i = 1; i < data.length; i++) {
                T key = data[i];
                int pos = i;
                while (pos > 0 && data[pos - 1].compareTo(key) > 0) {
                    data[pos] = data[pos - 1];
                    pos--;
                }
                data[pos] = key;
            }
        }
    //冒泡排序
    public static <T extends Comparable<? super T>> void bubbleSort(T[] data) {
            int pos;
            int scan;
            for (pos = data.length - 1; pos >= 0; pos--) {
                for (scan = 0; scan < pos; scan++) {
                    if (data[scan].compareTo(data[scan + 1]) > 0) {
                        swap(data, scan, scan + 1);
                    }
                }
            }
        }
    //快速排序
    public static <T extends Comparable<? super T>> void quickSort(T[] data) {
            quickSortRec(data, 0, data.length - 1);
        }
    private static <T extends Comparable<? super T>> void quickSortRec(T[] data, int begin, int end) {
            if (begin < end) {
                int mid = partition(data, begin, end);
                quickSortRec(data, begin, mid - 1);
                quickSortRec(data, mid + 1, end);
            }

        }
    private static <T extends Comparable<? super T>> int partition(T[] data, int min, int max) {

        T pa;
        int left, right;
        int mid = (min + max) / 2;
        // 将中点的data作为分割元素
        pa = data[mid];
        // 将分割元素前置到min处
        swap(data, mid, min);

        left = min;
        right = max;

        while (left < right) {
            while (left < right && data[left].compareTo(pa) <= 0) {
                left++;
            }
            while (data[right].compareTo(pa) > 0) {
                right--;
            }
            if (left < right)
                swap(data, left, right);
        }
        // 分割点置回中间位置
        swap(data, min, right);

        return right;
    }
    //归并排序
    public static <T extends Comparable<? super T>> void mergeSort(T[] data, int min, int max) {
            if (min < max) {
                int mid = (min + max) / 2;
                mergeSort(data, min, mid);
                mergeSort(data, mid + 1, max);
                merge(data, min, mid, max);
            }
        }
    private static <T extends Comparable<? super T>> void merge(T[] data, int first, int mid, int last) {
            T[] temp = (T[]) (new Comparable[data.length]);
            int first1 = first, last1 = mid;
            int first2 = mid + 1, last2 = last;

            int index = first1;
            while (first1 <= last1 && first2 <= last2) {
                if (data[first1].compareTo(data[first2]) < 0) {
                    temp[index] = data[first1];
                    first1++;
                } else {
                    temp[index] = data[first2];
                    first2++;
                }
                index++;
            }
            while (first1 <= last1) {
                temp[index] = data[first1];
                first1++;
                index++;
            }
            while (first2 <= last2) {
                temp[index] = data[first2];
                first2++;
                index++;
            }
            for (index = first; index <= last; index++)
                data[index] = temp[index];
        }
    //堆排序
    public static <T extends Comparable<? super T>> void heapSort(T[] data) {
        ArrayHeap<T> temp = new ArrayHeap<T>();
        for (int i = 0; i < data.length; i++)
            temp.addElement(data[i]);
        int count = 0;
        while (!(temp.isEmpty())) {
            data[count] = temp.removeMin();
            count++;
        }
    }
    //二叉树排序
    public static <T extends Comparable<? super T>> void binarytreeSort(T[] data){
        AVLTree tree = new AVLTree();
        for (int n = 0; n < data.length; n++){
            tree.addElement(data[n]);
        }
        tree.toInString();
    }
    //希尔排序
    public static <T extends Comparable<? super T>> void shellSort(T[] data){
        if(data == null || data.length <= 1){
            return;
        }
        int incrementNum = data.length/2;
        while(incrementNum >=1){
            for(int a = 0; a < data.length; a++){
                for(int b = a; b < data.length-incrementNum; b = b + incrementNum){
                    if(data[b].compareTo(data[b + incrementNum]) > 0){
                        T temple = data[b];
                        data[b] = data[b+incrementNum];
                        data[b+incrementNum] = temple;
                    }
                }
            }
            incrementNum = incrementNum / 2;
        }
        String result = "";
        for (int n = 0; n < data.length; n++){
            result += data[n] + " ";
        }
        System.out.println(result);
    }
    private static <T extends Comparable<? super T>> void swap(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
